package sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] a = {100, 250, 5, 6, 5, 85, 24, 14, 10, 52, 30, 15, 34, 64};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }

    /*
        1. gap循环从 a.length/2 到 1，修改 gap /= 2
        2. i循环，从gap递增到末尾
        3. 取出i位置的值存到临时变量
        4. j从i位置开始，向前 -=gap，j的范围>=gap
        5. 如果j-gap位置的值大，将这个值复制到j位置
           否则，结束j循环
        6. j循环结束后，临时值放到j位置
     */

    //希尔排序(就是插入排序的优化版，插入排序外层再套一个循环)
    private static void sort(int[] a) {
        for (int gap = a.length / 2; gap >= 1; gap /= 2) { //gap从a.length-2开始每次减少gap/2，到1结束
            //插入排序
            for (int i = gap; i < a.length; i++) { //i从gap的位置1开始递增到a.length
                int tmp = a[i];
                int j = i;
                for (; j >= gap && a[j - gap] > tmp; j -= gap) { //j从i位置(a.length)开始递减gap的值，直到j=gap
                    //可以把这个判断写到上面for循环条件中，那这里可以省略if-else
//                    if (a[j - gap] > tmp) {
                        a[j] = a[j - gap];
//                    } else {
//                        break;
//                    }
                }
                a[j] = tmp;
            }
        }
    }
}
